package baseclass.b_stackQueue;

import java.util.Stack;

/**
 * O(1)时间得到栈min
 *
 * @date 2020/2/27 17:44
 */
public class Code04_GetStackMin {
    private Stack<Integer> dataStack;
    private Stack<Integer> minStack;

    private int size = 0;
    public Code04_GetStackMin() {
        dataStack = new Stack<>();
        minStack = new Stack<>();
    }

    //方式1：两个栈的大小一样长
  /*  public void push(int e) {
        dataStack.push(e);
        if (minStack.size() == 0) minStack.push(e);
        //比较栈顶，只有比栈顶更小才入栈。
        if (minStack.peek() <= e) {
            minStack.push(minStack.peek());
        } else {
            minStack.push(e);
        }
    }

    public int pop() {
        int res = dataStack.pop();
        minStack.pop();
        return res;
    }*/

    //方式2：辅助站更短，如果没有出现更小的值，不更新
    public void push(int e){
        dataStack.push(e);
        if(minStack.size() == 0) {
            minStack.push(e);
            return;
        }
        //只放比栈顶相等或者更小的元素
        if(minStack.peek() >= e){
            minStack.push(e);
        }
        size ++;
    }
    public int pop(){
        int res = dataStack.pop();
        //只有最小栈顶和res相等，才出站
        if(minStack.peek() == res)
            minStack.pop();
        size -- ;
        return res;
    }

    public int getMin() {
        return minStack.peek();
    }

    public int getSize() {
        return size;
    }

    public static void main(String[] args) {
        Code04_GetStackMin stack = new Code04_GetStackMin();
        int[] arr = {2, 4, 0, 7, 8, -1};
        for (int i = 0; i < arr.length; i++) {
            stack.push(arr[i]);
            System.out.println("stack1的当前最小值:" + stack.getMin());
        }

        while (stack.size != 0) {
            //这样顺序会出现空栈。因为stack.pop的时候内部的minStack也会pop
            //假设size = 1，stack.pop后两个stack都是0，在执行stack.getMin出错
            //正确做法，先getMin，再pop.或者每次getMin前都要判断是否为空栈
            //stack.pop();
            //System.out.println("stack1的当前最小值:"+stack.getMin());
            System.out.println("stack1的当前最小值:" + stack.getMin());
            stack.pop();
        }

    }

}
